package com.zhj.interview;

import java.util.*;

public class Test12 {

    public static void main(String[] args) {
        Graph graph = new Graph(7);
        initGraph(graph);
        List<List<Vertex>> route = bfs(graph, 0, 6);
        List<Vertex> route2 = dfs(graph, 0, 6, new HashSet<>(), new ArrayList<>());

        System.out.println("广度优先遍历：");
        for (List<Vertex> vertices : route) {
            for (Vertex vertex : vertices) {
                System.out.print(vertex.data);
            }
            System.out.println();
        }
        System.out.println("深度优先遍历：");
        for (Vertex vertex : route2) {
            System.out.print(vertex.data);
        }
        System.out.println();
    }

    private static List<List<Vertex>> bfs(Graph graph, int start, int end) {
        List<List<Vertex>> result = new LinkedList<>();
        if (graph == null) {
            return result;
        }
        Set<Integer> set = new HashSet<>();
        // 顶点坐标
        Queue<Integer> queue = new LinkedList<>();
        // 起点坐标
        queue.add(start);
        set.add(start);
        Vertex[] vertices = graph.vertices;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Vertex> subList= new ArrayList<>();
            while (size > 0) {
                Integer index = queue.poll();
                subList.add(vertices[index]);
                // 添加周边节点坐标
                for (Edge edge : graph.adj[index]) {
                    if (!set.contains(edge.index)) {
                        set.add(edge.index);
                        queue.add(edge.index);
                    }
                }
                size--;
            }
            result.add(subList);
            if (queue.peek() == end) {
                break;
            }
        }
        return result;
    }

    private static List<Vertex> dfs(Graph graph, int start, int end, Set<Integer> set, List<Vertex> result) {
        result.add(graph.vertices[start]);
        set.add(start);
        for (Edge edge : graph.adj[start]) {
            if (!set.contains(edge.index)) {
                set.add(edge.index);
                dfs(graph, edge.index, end, set, result);
            }
        }
        return result;
    }

    private static class Vertex {
        String data;
        Vertex(String data) {
            this.data = data;
        }
    }

    private static class Edge {
        int index;
        Edge(int index) {
            this.index = index;
        }
    }

    private static class Graph {
        private Vertex[] vertices;
        private LinkedList<Edge> adj[];
        Graph(int size) {
            vertices = new Vertex[size];
            adj = new LinkedList[size];
            for (int i = 0; i < adj.length; i++) {
                adj[i] = new LinkedList<>();
            }
        }
    }


    private static void initGraph(Graph graph) {
        graph.vertices[0] = new Vertex("A");
        graph.vertices[1] = new Vertex("B");
        graph.vertices[2] = new Vertex("C");
        graph.vertices[3] = new Vertex("D");
        graph.vertices[4] = new Vertex("E");
        graph.vertices[5] = new Vertex("F");
        graph.vertices[6] = new Vertex("G");

        graph.adj[0].add(new Edge(1));
        graph.adj[0].add(new Edge(2));
        graph.adj[1].add(new Edge(0));
        graph.adj[1].add(new Edge(3));
        graph.adj[1].add(new Edge(5));
        graph.adj[2].add(new Edge(0));
        graph.adj[2].add(new Edge(3));
        graph.adj[2].add(new Edge(4));
        graph.adj[3].add(new Edge(1));
        graph.adj[3].add(new Edge(2));
        graph.adj[3].add(new Edge(4));
        graph.adj[3].add(new Edge(5));
        graph.adj[4].add(new Edge(2));
        graph.adj[4].add(new Edge(3));
        graph.adj[4].add(new Edge(6));
        graph.adj[5].add(new Edge(1));
        graph.adj[5].add(new Edge(3));
        graph.adj[5].add(new Edge(6));
        graph.adj[6].add(new Edge(4));
        graph.adj[6].add(new Edge(5));
    }
}
